95. Unique Binary Search Trees II

https://leetcode.com/problems/unique-binary-search-trees-ii/

題目介紹:

題目會給你一個數字 n，你要用範圍 1 to n 建立所有的二元搜尋樹(binary search trees)

Example1:

解法:

這題算是很基本的Divide and Conquer，所以有點不知道要打什麼

總之先上程式碼吧

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        
        def BST(arr):
            
            if len(arr) == 0:
                return [None]
            
            res = []
            for i in range(len(arr)):
                leftTree = BST(arr[:i])
                rightTree = BST(arr[i+1:])
                
                for l in leftTree:
                    for r in rightTree:
                        res.append(TreeNode(arr[i],l, r))
                        
            return res
                
        return BST([i for i in range(1, n+1)])

步驟:

1. 一開始先列出要建成節點的數字*[1~n]*
2. 接著按照BST的規則: 左子樹所有node的值小於根的值、右子樹所有node的值大於根的值，區分要建成左子樹和右子樹的數字，並建立左子樹leftTree和右子樹rightTree
3. 組成所有可能的結構

快一點的解法:

這個方法把輸入改成有開頭和結尾，並用一個 memory 去記下曾經組過的樹，若之後再次遇到同樣的開頭和結尾，就可以拿出儲存值省略一些步驟了

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        
        memory = {}
        def BST(start, end):
            
            if start > end:
                return [None]
            if (start, end) in memory:
                return memory[(start, end)]
            
            res = []
            for i in range(start, end+1):
                leftTree = BST(start, i-1)
                rightTree = BST(i+1, end)
                
                for l in leftTree:
                    for r in rightTree:
                        res.append(TreeNode(i, l, r))
                        
            memory[(start, end)] = res
            return res
                
        return BST(1, n)

閒聊:

今天是第二天，題目比昨天簡單一點

本來想說竟然都打這篇了，乾脆連他的類似題目Unique Binary Search Trees 也一起打

後來想想算了，過幾天後LeetCode可能就把這題當作當天的題目

所以之後遇到再說吧!